// 01背包问题，退课，待修改。

#include <bits/stdc++.h>
using namespace std;
int s[1000005], c[1000005];
int dp[1000005][105];
// dp[i][j] 表示前 i 门课，选了 j 门课的最小花费

int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> s[i] >> c[i];
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[i][j] = dp[i - 1][j]; // 不选第 i 门课
      if (j > 0 && j <= i) { // 选第 i 门课
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + c[i]);
      }
    }
  }

  cout << dp[n][n - k];

  return 0;
}
